This invention relates to packet switching systems; and more particularly, the invention relates to the scheduling and routing of packets corresponding to multiple streams of packets through a packet switching system.
The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ systems having greater speed and capacity (i.e., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Packet technology typically allows multiple information types to be transmitted over the same transmission lines and using the same packet switching systems and devices.
As used herein, the term xe2x80x9cpacketxe2x80x9d refers to generically addressable packets of all types, including fixed length cells and variable length packets. Moreover, these packets may contain one or more types of information, including, but not limited to, voice, data, video, and audio information. Furthermore, the term xe2x80x9csystemxe2x80x9d is used generically herein to describe any number of components, packet switches, networks, computer and/or communication devices or mechanisms, or combinations thereof.
Consumers and designers of these systems typically desire increased performance at a reasonable price. A commonly used technique for helping to achieve this goal is for these systems to provide multiple paths between a source and a destination. Packets of information are then dynamically routed and distributed among these multiple paths. It is typically more cost-effective to provide multiple slower rate links or switching paths, than to provide a single higher rate path. Such designs also achieve other desired performance characteristics.
However, this approach can lead to network congestion, especially for certain types of traffic. Packet switching systems route all kinds of traffic, including point-to-point or circuit switched traffic. This traffic includes isochronous traffic that arrives at an input port and is routed to one or more output ports of the packet switching system. For example, a Synchronous Optical Network (SONET) OC-192 link might be terminated on an input port with numerous OC-3 and OC-1 streams of data being routed through the packet switching system. The uncoordinated routing of such traffic, and especially when multiple streams arriving at multiple inputs of a packet switch, can lead to some unbounded network congestion conditions. Needed are new methods and systems for routing such traffic to achieve bounded delay in the packet switching system.
Packet switches, systems apparatus and methods are disclosed for scheduling and routing packets through a packet switching system. In one embodiment, a packet switch has an input interface, an output interface and an interconnection network coupled to the first input and output interfaces. The input interface includes a packet route scheduler which schedules the forwarding of packets over a multiplicity of different paths in such a way as to limit contention for internal links in the interconnection network so as to ensure that packets pass through the interconnection network with bounded delay.